package labuladong.动态规划;

public class 高楼扔鸡蛋 {
    public static int dropEgg(int K, int N) {
        int[][] dpArr = new int[K+1][N+1];
        return dp(K, N, dpArr);
    }

    public static int dp(int K, int N, int[][] dpArr) {
        if (K == 1) {
            return N; // 只有一个鸡蛋
        }
        if (N == 0) {
            return 0; // 0层楼
        }

        if (dpArr[K][N] != 0) {
            return dpArr[K][N];
        }
        int res = Integer.MAX_VALUE;
        for (int i=1; i<=N; i++) {
            res = Math.min(res, Math.max(dp(K, N-i, dpArr), dp(K-1, i-1, dpArr))+1);
        }
        dpArr[K][N] = res;
        return res;
    }

    public static void main(String[] args) {
        System.out.println(dropEgg(1, 7));
    }
}
